PROGRAMACIÓN GENÉRICA

“Pensar es olvidar diferencias, es generalizar, abstraer” (Borges)

“Pensamos en generalidades, pero vivimos en detalles” (A.N. Whitehead)

“Siempre se debe generalizar” (Carl Jacobi)

“Lo genérico puede ser más intenso que lo concreto” (Borges)

---

Programación Genérica
La programación genérica es una técnica de desarrollo de componentes de software tan generales como sea posible, con varios objetivos:

1. Para que los componentes se puedan reutilizar en otras aplicaciones.
   
   
2. Para que dependan lo menos posible del entorno de ejecución, se ignoren los detalles implementadores y se consiga la interoperabilidad.
   
   
3. Para que los desarrollos sean más conceptuales e inteligibles.

Por ejemplo, un algoritmo podría apoyarse en conceptos generales, tales como: recorrer una estructura de datos, acceder a uno de sus elementos, seleccionar los elementos que cumplen determinadas condiciones, etc.

Aunque estos objetivos son deseables y beneficiosos, existen algunos inconvenientes:

1. Los desarrollos pueden ser menos eficientes. Generalidad y eficiencia son, en general, fuerzas opuestas.
   
   
2. Si el lenguaje de programación no es de alto nivel, los desarrollos genéricos pueden ser más extensos que los específicos. Esto es debido al código adicional necesario para analizar el tipo de cada argumento, el diferente tratamiento asociado a cada tipo, la posible inclusión de parámetros adicionales, etc.

La implementación de la programación genérica depende fundamentalmente del lenguaje utilizado y del nivel de abstracción que soporta.


Los aspectos genéricos

El concepto “genérico” en programación genérica tiene diferentes aspectos:

• En componentes parametrizados, se refiere a que los parámetros no están limitados a un cierto tipo de datos. Es lo que se denomina “polimorfismo paramétrico”.
  
  Es frecuente el tener que escribir diferentes versiones de un mismo componente para diferentes tipos de datos. Por ejemplo, una función para clasificar números, otra para clasificar cadenas de caracteres, etc. Lo ideal es que hubiera una función genérica de clasificación, que sirviera para todo tipo de elementos. Otro ejemplo sería un algoritmo de búsqueda que funcionara con listas, ficheros, matrices, etc., así como con porciones de estas estructuras.
  
  
• En componentes parametrizados, que el número de parámetros sea variable.
  
  
• En componentes que producen un resultado, que éste no se limite a ciertos tipos de datos, sino que pueda ser cualquier tipo de expresión: un dato, una estructura, una clase, un objeto, una función, un conjunto, etc.
  
  
• Que puedan definirse componentes software de orden superior, por ejemplo: funciones que devuelvan funciones, objetos compuestos de objetos, clases de clases, etc.
  
  
• Que puedan realizarse combinaciones de diferentes tipos de elementos, por ejemplo: funciones que devuelven objetos, clases de funciones, estructuras formadas por procedimientos, conjuntos de objetos, etc.

Implementación en MENTAL
La programación genérica alcanza su máxima plenitud en este lenguaje, pues cubre todos los aspectos mencionados:

• MENTAL es un lenguaje genérico porque las primitivas del lenguaje son universales y, por lo tanto, genéricas. Al utilizarse conceptos universales, los desarrollos tienden a ser genéricos.
  
  
• Muchas operaciones derivadas, como longitud, profundidad, selección de elementos, etc. son genéricas, es decir, son independientes del tipo de los argumentos. Y si los argumentos no son del tipo exigido y no puede realizarse la operación, entnces el resultado es la propia operación. Por ejemplo:
  
  
  a+b // se autoevalúa

(a…a+5) // rep. a a+1 a+2 a+3 a+4 a+5

a/(b=3) // se autoevalúa
  
  
• La combinatoria de primitivas es genérica, es decir, las primitivas son ortogonales y pueden combinarse libremente.
  
  
• Se pueden especificar expresiones genéricas (parametrizadas o no).
  
  
• La reutilización es general: se aplica a todo tipo de expresiones.

Ejemplos

1. Copiar los n primeros elementos de la secuencia x en la secuencia y. Supone n>0.
   
   ⟨( Copiar(x y n) = [y\i = x\i)/(i=[1…n])] )⟩
   
   Esta función es válida para cualquier secuencia, independientemente del tipo de sus componentes.
   
   Ejemplo de aplicación:
   
   
   x=(a (b c) 17.4 {d e} u v)

y=(1 2 3 4 5 6)

Copiar(x y 4) // copiar los primeros 4 elementos de x en y

y // ev. (a (b c) 17.4 {d e} 5 6)
   
   
2. Sustituir los n primeros elementos de la secuencia x por el elemento y. Supone n>0

⟨( Sustituir(x n y) = [x\i = y)/(i=[1…n])] )⟩
   
   Ejemplos de aplicación:
   
   
   x=(a (b c) 17.4 {d e} u v)

Sustituir(x 4 y)

x // ev. (y y y y u v)

x=(a (b c) 17.4 {d e} u v)

Sustituir(x 2 (s1 s2))

x // ev. ((s1 s2) (s1 s2) 17.4 {d e} u v)
   
   
3. Sumar todos los componentes de una secuencia.
   En este caso, hay un único parámetro (la secuencia), cuyo número de elementos es variable. Equivale, en definitiva, a un número variable de parámetros.
   
   
   ⟨( Sumar(x) = +⊣x )⟩
   
   Ejemplos de aplicación:
   
   
   Sumar(1 2 3 4) // ev. 10

Sumar(1234) // ev. 10

Sumar(a b c d) // ev. a+b+c+d

Sumar(abcd) // ev. a+b+c+d

Sumar(a 1 b 2 c 3) // ev. a+b+c+6

---

Adenda
Historia de la programación genérica

El lenguaje Lisp se puede considerar implícitamente como el primer lenguaje de programación genérica, gracias a su alto nivel de abstracción, su sistema unificado de almacenamiento de código y datos (las listas), sus tipos dinámicos, su capacidad de parametrización y la posibilidad de trabajar con funciones de orden superior.

El lenguaje C++ es el primer lenguaje en soportar explícitamente dos mecanismos genéricos:

• Las plantillas.
  Una plantilla es una especie de molde de código, a partir del cual el compilador puede generar instancias específicas. Las plantillas se utilizan para crear bibliotecas de código de propósito general.
  
  
• Los operadores polimórficos.
  Un operador polimórfico (también llamado “sobrecargado”) es aquel que puede funcionar con diferentes tipos de datos.

C++ es un lenguaje que no tiene versiones. El estándar ANSI/ISO (1988) define el núcleo del lenguaje. C++ es multiparadigma (orientado a objetos, funcional y procedimental).

La eficiencia de un algoritmo puede ser relativa si es tan eficiente como la versión no genérica (escrita en el mismo lenguaje) y absoluta si es tan eficiente como una versión no genérica escrita en lenguaje ensamblador. Con C++ se ha conseguido una eficiencia relativa y aproximarse a la absoluta, de tal forma que eficiencia y generalidad no sean mutuamente exclusivas.

Se considera que la verdadera programación genérica nació con el trabajo de Alexander Stepanov con el lenguaje Ada y que posteriormente traslado a C++ para crear la STL (Standard Template Library, Biblioteca de Plantillas Estándar), biblioteca de componentes genéricos de software implementados como plantillas, que fue adoptada como estándar ANSI/ISO del lenguaje. A esta biblioteca siguieron otras, también de tipo genérico, como la Boost Graph Library y la Matrix Template Library. C++ se convirtió entonces en un lenguaje multiparadigma enriquecido con la programación genérica.

La programación genérica es un paradigma que ha ido cobrando una creciente importancia, de tal forma que, en los últimos años, muchos lenguajes (como Stándard ML, Haskell, Eiffel y Java) han incorporado mecanismos genéricos (al menos de forma básica), inspirados principalmente por el modelo STL. Lenguajes específicos recientes de programación genérica son Generic Haskell (2000) y Generic C# (2003).


STL

La biblioteca de plantillas de C++ fue diseñada para lograr la máxima reusabilidad sin sacrificar la eficiencia. Su importancia radica en sus conceptos (o categorías abstractas), más que en los detalles implementadores. Las fuentes STL tienen la sintaxis C. Es posible incluso programar en STL sin saber C++. Entre estos conceptos los más destacados son los siguientes:

• Contenedores (containers).
  Son objetos que pueden contener objetos de cualquier tipo (enteros, punteros, caracteres, etc.), incluso tipos definidos por el usuario.
  
  Existen diferentes tipos de contenedores, según la organización de sus elementos y formas de acceso: vector, array, lista, cola, cola doble (deque), pila, mapa, conjunto, y bitset (conjunto de valores boleanos).
  
  
• Iteradores (iterators).
  Son una especie de punteros generalizados que actúan como enlace entre los algoritmos y los contenedores.
  
  Existen 5 tipos de iteradores: 3 para recorrer un contenedor (hacia delante, bidireccional y de acceso directo) y 2 para leer o actualizar un elemento del contenedor (iterador de entrada y de salida).
  
  Cada tipo de contenedor utiliza los iteradores más adecuados ara asegurarse una implementación eficiente.
  
  
• Adaptadores (adapters).
  Son modificadores de otros componentes. Hay varias clases, por ejemplo: el adaptador “pila” (stack), que convierte un contenedor en una simple pila; el adaptador “iterador contrario” (reverse iterator), que invierte el movimiento de un iterador, etc.
  
  
• Objetos función (function objects).
  Son objetos que pueden invocarse como si fueran funciones. Un objeto función que devuelve un valor boleano se denomina “objeto predicado” (predicate object).

Bibliografía

• Alexandrescu, Andrei. Modern C++ Design. Generic Programming and Design Patterns Applied. Addison-Wesley Professional, 2001.
  
  
• Austern, Matthew H. Generic Programming and the STL: Using and Extending the C++ Standard Template Library. Addison-Wesley, 1998.
  
  
• Backhouse, Roland; Gibbons, Jeremy (editors). Generic Programming. Advanced Lectures Lecture Notes in Computer Science, Springer, 2003.
  
  
• García, R.; Järvi, J.; Lumsdaine, A.; Siek, J.G. ; Willcock, J. A comparative study of language support for generic programming. In OOSPLA, Oct. 2003.
  
  
• Musser, David R.; Derge, Gillmer J.; Saini, Atud. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library. Addison-Wesley, 2001.
  
  
• Stepanov, Alexander. The Standard Template Library – how do you build an algorithm that is both generic and efficient? Byte Magazine, 20 (10), Oct. 1995.
  
  
• Web STL de Silicon Graphics Computer Systems, Inc.: http://www.sgi.com/tech/stl/